package main

import "fmt"

var results [][]int

func combinationSum(candidates []int, target int) [][]int {
	results = nil
	backtrack(candidates, target, nil, 0)
	return results
}

func backtrack(candidates []int, target int, result []int, beg int) {
	sum := 0
	for _, v := range result {
		sum += v
	}
	if sum == target {
		var r0 []int
		r0 = append(r0, result...)
		results = append(results, r0)
		return
	}
	if sum > target {
		return
	}
	for i := beg; i < len(candidates); i++ {
		v := candidates[i]
		result = append(result, v)
		backtrack(candidates, target, result, i)
		result = result[0 : len(result)-1]
	}
}

func main() {
	r := combinationSum([]int{2, 3, 6, 7}, 7)
	fmt.Printf("%v\n", r)
	r = combinationSum([]int{2, 3, 5}, 8)
	fmt.Printf("%v", r)
}
